/**
 * @Author wonghiu
 * @Date 2021/8/21 10:50
 * @Version 1.0.1
 */
public class youzan {
    public static void main(String[] args) {
        new youzan().new Solution().isMatch("aa","a");

    }

    class Solution {

        public boolean isMatch(String str, String pat) {
            // write code here
            str = " " + str;
            pat = " " + pat;
            System.out.println(pat.length());
            boolean[][] dp = new boolean[str.length()][pat.length()];

            dp[0][0] = true;
            for (int i = 0; i < dp.length; i++) {
                for (int j = 1; j < dp[0].length; j++) {
                    // pat的后一个为*，则pat不可单独考虑，跳过
                    if (j + 1 <= dp[0].length-1 && pat.charAt(j + 1) == '*') {
                        continue;
                    } else if (i - 1 >= 0 && pat.charAt(j) == '.') {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (pat.charAt(j) == '*') {
                        dp[i][j] = (j - 2 >= 0 && dp[i][j - 2]) || (i - 1 >= 0 && dp[i - 1][j]);

                    } else {
                        dp[i][j] = i - 1 >= 0 && dp[i - 1][j - 1] && str.charAt(i) == pat.charAt(j);
                    }

                }
            }
            return dp[dp.length - 1][dp[0].length - 1];
        }
    }
}